NOIP2008 普及组
T1:ISBN号码
题目描述
每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括位数字、位识别码和位分隔符，其规定格式如x-xxx-xxxxx-x，其中符号-就是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如代表英语；第一个分隔符-之后的三位数字代表出版社，例如代表维京出版社；第二个分隔符后的五位数字代表该书在该出版社的编号；最后一位为识别码。
识别码的计算方法如下：
首位数字乘以加上次位数字乘以……以此类推，用所得的结果，所得的余数即为识别码，如果余数为，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码是这样得到的：对067082162这个数字，从左至右，分别乘以再求和，即，然后取的结果作为识别码。
你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出Right；如果错误，则输出你认为是正确的ISBN号码。
输入输出格式
输入格式：
一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。
输出格式：
一行，假如输入的ISBN号码的识别码正确，那么输出Right，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符-）。
输入输出样例
输入样例#1：
0-670-82162-4
输出样例#1：
Right
输入样例#2：
0-670-82162-0
输出样例#2：
0-670-82162-4
说明
2008普及组第一题
题解：
本题直接模拟就可以。设置一个变量 ，表该这个数字该乘几了。然后读入这个 号码，如果是数字的话那么便 ，最后让识别码 ，接着特判一下识别码是不是 就可以了。
#include <iostream>
using namespace std;
char ISBN[15]; //存储图书ISBN号
int main() {
int num = 0; //存储正确的识别码
int k = 1; //第几个数字
for (int i = 1; i <= 12; i++) {
cin >> ISBN[i];
if (ISBN[i] >= '0' && ISBN[i] <= '9') { //找到一个数字
num += ((ISBN[i] - '0') * k);
k++;
}
}
num %= 11; //将所得的结果mod11，所得的余数即为识别码
cin >> ISBN[13]; //读入识别码
if (num != 10)
if (num == ISBN[13] - '0')
cout << "Right" << endl;
else {
for (int i = 1; i <= 12; i++)
cout << ISBN[i];
cout << num << endl;
}
else
if (ISBN[13] == 'X')
cout << "Right" << endl;
else {
for (int i = 1; i <= 12; i++)
cout << ISBN[i];
cout << "X" << endl;
}
return 0;
}
T2:排座椅
题目描述
上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的对同学上课时会交头接耳。
同学们在教室中坐成了行列，坐在第行第j列的同学的位置是，为了方便同学们进出，在教室中设置了条横向的通道，条纵向的通道。
于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了个会交头接耳的同学，那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生的对数最少。
输入输出格式
输入格式：
第一行，有个用空格隔开的整数，分别是
接下来的行，每行有个用空格隔开的整数。第行的个整数，表示坐在位置与的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。
输入数据保证最优方案的唯一性。
输出格式：
共两行。 第一行包含个整数，表示第行和行之间、第行和行之间、…、第行和第行之间要开辟通道，其中，每两个整数之间用空格隔开（行尾没有空格）。
第二行包含个整数，表示第列和列之间、第列和列之间、…、第列和第列之间要开辟通道，其中，每两个整数之间用空格隔开（列尾没有空格）。
输入输出样例
输入样例#1：
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
输出样例#1：
2
2 4
说明
上图中用符号*、※、+标出了对会交头接耳的学生的位置，图中条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。
2008年普及组第二题
题解：
我们读完这道题目，就想到本题可以用贪心的思想来解决。
在读入 之后，我们找哪里可以将两人分开。例如，当 时，则代表两人的横坐标相同，纵坐标不同，所以应该在平行于 轴的地方将两人分开。我们用 数组表示平行于 轴的道路，用 数组表示平行于 轴的道路。 则当 时， ；当 时，应该在平行于 轴的地方将两人分开，所以 。
接着，我们依次枚举 数组最大的前 项与 数组最大的前 项，将其按序号从小到大排序输出，便得到我们的答案辣！
#include <iostream>
#include <algorithm>
using namespace std;
int H[1001], L[1001];
int a[1001]; //存储要选择的数字
int main() {
int m, n, k, l, d; //同学们在教室中坐成了m行m列，设置了K条横向的通道，L条纵向的通道，只有有限的D对同学上课时会交头接耳
cin >> m >> n >> k >> l >> d;
int x, y, p, q; //表示坐在位置(x,y)与(p,q)的两个同学会交头接耳
for (int i = 1; i <= d; i++) {
cin >> x >> y >> p >> q;
if (x == p) //两人的横坐标相同，纵坐标不同，应在L数组将两人分开
L[min(y, q)]++;
else //两人的纵坐标相同，横坐标不同，应在H数组将两人分开
H[min(x, p)]++;
}
int w = 0;
for (int i = 1; i <= k; i++) { //选横着要在哪里设走廊
int maxx = 0, bh = 0;
for (int j = 1; j <= m; j++)
if (H[j] > maxx) {
maxx = H[j];
bh = j;
}
w++;
a[w] = bh;
H[bh] = 0;
}
sort(a + 1, a + 1 + k);
for (int i = 1; i <= k; i++)
cout << a[i] << " ";
w = 0;
cout << endl;
for (int i = 1; i <= l; i++) { //选竖着要在哪里设走廊
int maxx = 0, bh = 0;
for (int j = 1; j <= n; j++)
if (L[j] > maxx) {
maxx = L[j];
bh = j;
}
w++;
a[w] = bh;
L[bh] = 0;
}
sort(a + 1, a + 1 + l);
for (int i = 1; i <= l; i++)
cout << a[i] << " ";
return 0;
}
T3:传球游戏
题目描述
上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。
游戏规则是这样的：个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是败者，要给大家表演一个节目。
聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了次以后，又回到小蛮手里。两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有三个同学号、号、号，并假设小蛮为号，球传了次回到小蛮手里的方式有->->->和->->->，共种。
输入输出格式
输入格式：
一行，有两个用空格隔开的整数。
输出格式：
个整数，表示符合题意的方法数。
输入输出样例
输入样例#1：
3 3
输出样例#1：
2
说明
的数据满足：
的数据满足：
2008普及组第三题
题解：
一个 问题。
游戏开始之后，每个人手中的球要么是从他左边传过来的，要么是从他右边传过来的，所以第 轮时球回到第 个人手里的方式总数也就是上一轮时球回到第 个人的方案总数 上一轮时球回到第 个人的方案总数。我们化环为链，用 来表示在第 轮时回到第 个人手里的方式总数。因此，便可以得到 。考虑边界条件，在一开始时，球在第一个人手里，所以 。然后考虑到特殊情况，当 或 时，要进行特殊处理，特殊处理比较简单，所以。。。就直接看代码吧！
#include <iostream>
using namespace std;
int DP[31][31];
int main() {
int n, m;
cin >> n >> m; //n个同学m轮
DP[0][1] = 1; //边界条件
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (j == 1)
DP[i][j] = DP[i - 1][j + 1] + DP[i - 1][n];
else if (j == n)
DP[i][j] = DP[i - 1][1] + DP[i - 1][j - 1];
else
DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1];
DP[m][1] = DP[m - 1][2] + DP[m - 1][n];
cout << DP[m][1] << endl;
return 0;
}
T4:立体图
题目描述
小渊是个聪明的孩子，他经常会给周围的小朋友们讲些自己认为有趣的内容。最近，他准备给小朋友们讲解立体图，请你帮他画出立体图。
小渊有一块面积为的矩形区域，上面有个边长为的格子，每个格子上堆了一些同样大小的积木（积木的长宽高都是），小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式，并且不会做任何翻转旋转，只会严格以这一种形式摆放：
+---+
/ /|
+---+ |
| | +
| |/
+---+
每个顶点用个加号’+’表示，长用个”-“表示，宽用个”/”表示，高用两个”|”表示。字符’+’ ‘-‘’/’ ‘|’的ASCII码分别为，，，。字符’.’（ASCII码）需要作为背景输出，即立体图里的空白部分需要用’.’代替。立体图的画法如下面的规则：
若两块积木左右相邻，图示为：
..+---+---+
./ / /|
+---+---+ |
| | | +
| | |/.
+---+---+..
若两块积木上下相邻，图示为：
..+---+
./ /|
+---+ |
| | +
| |/|
+---+ |
| | +
| |/.
+---+..
若两块积木前后相邻，图示为：
....+---+
.../ /|
..+---+ |
./ /| +
+---+ |/.
| | +..
| |/...
+---+....
立体图中，定义位于第的格子（即第行第列的格子）上面自底向上的第一块积木（即最下面的一块积木）的左下角顶点为整张图最左下角的点。
输入输出格式
输入格式：
第一行有用空格隔开的个整数和，表示有个格子。
接下来的行，是一个的矩阵，每行有个用空格隔开的整数，其中第行第列上的整数表示第行第列的格子上摞有多少个积木（每个格子上的积木数）。
输出格式：
输出包含题目要求的立体图，是一个行列的字符串矩阵，其中和表示最少需要行列才能按规定输出立体图。
输入输出样例
输入样例#1：
3 4
2 2 1 2
2 2 1 1
3 2 1 2
输出样例#1：
......+---+---+...+---+
..+---+ / /|../ /|
./ /|-+---+ |.+---+ |
+---+ |/ /| +-| | +
| | +---+ |/+---+ |/|
| |/ /| +/ /|-+ |
+---+---+ |/+---+ |/| +
| | | +-| | + |/.
| | |/ | |/| +..
+---+---+---+---+ |/...
| | | | | +....
| | | | |/.....
+---+---+---+---+......
说明
NOIP2008普及组第四题
题解：
这个题用打表的方法就可以。。。按照从后先前，从下向上，从左向右地顺序构建立体图就能做出此题。
#include <iostream>
using namespace std;
char canvas[1001][1001];
int num[51][51]; //第i行第j列的个子上摞有多少个积木
int m, n;
int c, k; //计算画布的长度与宽度
void draw(int x, int y) {
canvas[x][y] = '+';
canvas[x][y + 1] = '-';
canvas[x][y + 2] = '-';
canvas[x][y + 3] = '-';
canvas[x][y + 4] = '+';
canvas[x - 1][y] = '|';
canvas[x - 1][y + 1] = ' ';
canvas[x - 1][y + 2] = ' ';
canvas[x - 1][y +3] = ' ';
canvas[x - 1][y + 4] = '|';
canvas[x - 1][y + 5] = '/';
canvas[x - 2][y] = '|';
canvas[x - 2][y + 1] = ' ';
canvas[x - 2][y + 2] = ' ';
canvas[x - 2][y + 3] = ' ';
canvas[x - 2][y + 4] = '|';
canvas[x - 2][y + 5] = ' ';
canvas[x - 2][y + 6] = '+';
canvas[x - 3][y] = '+';
canvas[x - 3][y + 1] = '-';
canvas[x - 3][y + 2] = '-';
canvas[x - 3][y + 3] = '-';
canvas[x - 3][y + 4] = '+';
canvas[x - 3][y + 5] = ' ';
canvas[x - 3][y + 6] = '|';
canvas[x - 4][y + 1] = '/';
canvas[x - 4][y + 2] = ' ';
canvas[x - 4][y + 3] = ' ';
canvas[x - 4][y + 4] = ' ';
canvas[x - 4][y + 5] = '/';
canvas[x - 4][y + 6] = '|';
canvas[x - 5][y + 2] = '+';
canvas[x - 5][y + 3] = '-';
canvas[x - 5][y + 4] = '-';
canvas[x - 5][y + 5] = '-';
canvas[x - 5][y + 6] = '+';
}
int main() {
cin >> m >> n;
k = 2 * m + 4 * n + 1;
for (int i = 1; i <= 1000; i++)
for (int j = 1; j <= 1000; j++)
canvas[i][j] = 46; //初始化画布
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
cin >> num[i][j];
c = max(c, num[i][j] * 3 + 2 * (m - i + 1) + 1);
}
int x = 1, y = 1;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
x = c - 2 * (m - i);
y = 2 * (m - i) + 4 * (j - 1) + 1;
while (num[i][j] > 0) {
draw(x, y);
num[i][j]--;
x -= 3;
}
}
for (int i = 1; i <= c; i++) {
for (int j = 1; j <= k; j++)
cout << canvas[i][j];
cout << endl;
}
return 0;
}